/**
 快速排序（Quicksort）是对冒泡排序的一种改进。

 基本思路：
 1.以一个数作为基准（以下是以中间数），比基数小的数放在左边，比基数大的数放在右边
 2.按照此方法对两分布数据分别进行快速排序（递归进行）
 3.不能再分后退出递归，并重新将数组合并
 */



function quickSort(arr){
    //如果数组长度小于等于1无需判断直接返回即可
    if(arr.length <= 1){
        return arr
    }
    //pivotIndex 基础索引
    let pivotIndex = Math.floor(arr.length / 2)
    //找到基础，并且把基础从原来的数组中删除
    let pivot = arr.splice(pivotIndex,1)[0]
    //定义左右数组
    let left = []
    let right = []
    //比基准小的放在left,比基准大德放在right
    arr.forEach(item => {
        if(item < pivot){
            left.push(item)
        }else{
            right.push(item)
        }
    })
    return [...quickSort(left),pivot,...quickSort(right)]
}



var array=[2,5,7,3,6,4,1];
// array=[1,2,3,4,5];
console.log(quickSort(array).toString());
